/**
 * @file ChildSiblingTree.c
 * @desc 使用「孩子-兄弟表示法」实现树的存储结构及基本操作，包括创建节点、构建示例树、递归打印和释放内存。
 * @author WangBlue (wangjiping596@gmail.com)
 * @date 2025/10/17 11:35
 * @version 1.0
 */

#include <stdio.h>
#include <stdlib.h>

/**
 * @struct csNode
 * @brief 孩子-兄弟表示法树节点
 *
 * @var data        节点存储的数据（此处使用 int，可存储字符的 ASCII 值）
 * @var firstChild  指向第一个孩子节点
 * @var nextSibling 指向下一个兄弟节点
 */
typedef struct csNode {
    int data;
    struct csNode *firstChild;
    struct csNode *nextSibling;
} csNode;

/**
 * @brief 创建一个新的孩子-兄弟树节点
 * @param data 节点数据（字符 ASCII 值）
 * @return 成功返回节点指针，失败返回 NULL
 */
csNode* createNode(int data) {
    csNode *temp = (csNode *)malloc(sizeof(csNode));
    if (temp == NULL) return NULL;

    temp->data = data;
    temp->firstChild = NULL;
    temp->nextSibling = NULL;
    return temp;
}

/**
 * @brief 创建一个示例树（孩子-兄弟表示法）
 *
 * 树的逻辑结构（ASCII 表示节点）：
 * ```
 *        A
 *       /
 *      B
 *     /
 *    C -- D
 *   /
 *  E -- F
 * ```
 * - `firstChild` 指向第一个孩子
 * - `nextSibling` 指向兄弟节点
 *
 * @return 返回树的根节点指针
 */
csNode* createSimpleTree() {
    csNode* A = createNode('A');
    csNode* B = createNode('B');
    csNode* C = createNode('C');
    csNode* D = createNode('D');
    csNode* E = createNode('E');
    csNode* F = createNode('F');

    // 建立孩子-兄弟关系
    A->firstChild = B;
    B->firstChild = C;
    C->firstChild = E;
    C->nextSibling = D;

    E->nextSibling = F;

    return A;
}

/**
 * @brief 递归打印孩子-兄弟树（先序遍历）
 * @param node 当前节点指针
 *
 * @note
 * 先打印节点本身，再递归打印第一个孩子，最后递归打印兄弟节点。
 */
void printTree(csNode* node) {
    if (!node) return;

    printf("%c ", node->data);

    // 递归打印第一个孩子
    printTree(node->firstChild);

    // 递归打印兄弟节点
    printTree(node->nextSibling);
}

/**
 * @brief 递归释放孩子-兄弟树的所有节点
 * @param node 当前节点指针
 *
 * @note
 * 先释放孩子节点，再释放兄弟节点，最后释放自身。
 */
void freeTree(csNode* node) {
    if (!node) return;
    freeTree(node->firstChild);
    freeTree(node->nextSibling);
    free(node);
}

/**
 * @brief 主函数：创建示例树，打印树结构，并释放内存
 */
int main() {
    csNode* root = createSimpleTree();

    printf("child-sibling representation(pre-order): \n");
    printTree(root);
    printf("\n");

    freeTree(root);
    return 0;
}
